package leetcode_core.leetcode_5;

import org.junit.Test;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年01月09日 17:42
 */
public class SearchMatrix {
    public boolean searchMatrix(int[][] matrix, int target) {
        //先在列里面二分,找到一个合适的位置,使得matrix[i][0]<=target<=matrix[i+1][0]
        int l = 0,r = matrix.length;
        //定义搜索区间[l,r],当l<=r的时候,区间依然存在,可以搜索
        int row = -1;
        if(matrix[0][0] > target){
            return false;
        }
        while(l<=r){
            int mid = (l+((r-l)>>1));//右移1bit=/2
            if(mid == matrix.length-1){
                row = mid;
                break;
            }
            if(matrix[mid][0] == target){
                return true;
            }
            if(matrix[mid][0] < target && matrix[mid+1][0]> target){
                //那么这个mid就是我们要找的
                row = mid;
                break;
            }else if(matrix[mid][0] > target){
                r = mid-1;
            }else if(matrix[mid][0] < target){
                l = mid+1;
            }
        }
        if(row == -1){
            return false;
        }
        l = 0;r = matrix[0].length;
        while (l<=r){
            int mid = (l+((r-l)>>1));
            if(target == matrix[row][mid]){
                return true;
            }else if(matrix[row][mid] > target){
                r = mid-1;
            }else if(matrix[row][mid] < target){
                l = mid+1;
            }
        }
        return false;
    }
    @Test
    public void test(){
        System.out.println(searchMatrix(new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}}, 13));
    }
}
